/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.array

import org.jheaps.AddressableHeap
import org.jheaps.Constants
import org.jheaps.annotations.ConstantTime
import org.jheaps.annotations.LogarithmicTime
import java.io.Serializable
import kotlin.math.max

/**
 * Abstract implementation of a heap using an array representation.
 *
 * @author Dimitrios Michail
 *
 * @param <K>
 * the type of keys maintained by this heap
</K> */
abstract class AbstractArrayAddressableHeap<K, V>(comparator: Comparator<in K?>?, capacity: Int) :
    AddressableHeap<K, V>, Serializable {
    /**
     * The comparator used to maintain order in this heap, or null if it uses
     * the natural ordering of its keys.
     *
     * @serial
     */
    protected var comparator: Comparator<in K?>?

    /**
     * The array use for representing the tree.
     */
    protected var array: Array<ArrayHandle?>

    /**
     * Number of elements in the heap.
     */
    protected var size: Int

    /**
     * Minimum capacity due to initially requested capacity.
     */
    protected val minCapacity: Int

    /**
     * {@inheritDoc}
     */
    init {
        checkCapacity(capacity)
        this.size = 0
        this.comparator = comparator
        this.minCapacity = max(capacity.toDouble(), DOWNSIZING_MIN_HEAP_CAPACITY.toDouble()).toInt()
        this.array = arrayOfNulls(minCapacity + 1)
            //java.lang.reflect.Array.newInstance(ArrayHandle::class.java, minCapacity + 1) as Array<ArrayHandle?>
    }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun findMin():ArrayHandle{
        if (Constants.NOT_BENCHMARK && size == 0) {
            throw NoSuchElementException()
        }
        return array[1]!!
    }

    @get:ConstantTime
    override val isEmpty: Boolean
        get() {
            return size == 0
        }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun size(): Long {
        return size.toLong()
    }

    /**
     * {@inheritDoc}
     */
    override fun comparator(): Comparator<in K?>? {
        return comparator
    }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun clear() {
        size = 0
    }

    /**
     * {@inheritDoc}
     */
    @LogarithmicTime(amortized = true)
    override fun insert(key: K): ArrayHandle {
        return insert(key, null)
    }

    /**
     * {@inheritDoc}
     */
    @LogarithmicTime(amortized = true)
    override fun insert(key: K, value: V?): ArrayHandle{
        if (Constants.NOT_BENCHMARK) {
            if (key == null) {
                throw NullPointerException("Null keys not permitted")
            }
            // make sure there is space
            if (size == array.size - 1) {
                if (array.size == 1) {
                    ensureCapacity(1)
                } else {
                    ensureCapacity(2 * (array.size - 1))
                }
            }
        }

        val p = ArrayHandle(key, value)
        size++
        array[size] = p
        p.index = size

        if (comparator == null) {
            fixup(size)
        } else {
            fixupWithComparator(size)
        }

        return p
    }

    /**
     * {@inheritDoc}
     */
    @LogarithmicTime(amortized = true)
    override fun deleteMin(): ArrayHandle {
        if (Constants.NOT_BENCHMARK && size == 0) {
            throw NoSuchElementException()
        }

        val result = array[1]!!
        result.index = NO_INDEX
        if (size == 1) {
            array[1] = null
            size = 0
        } else {
            array[1] = array[size--]
            if (comparator == null) {
                fixdown(1)
            } else {
                fixdownWithComparator(1)
            }
        }

        if (Constants.NOT_BENCHMARK) {
            if (2 * minCapacity < array.size - 1 && 4 * size < array.size - 1) {
                ensureCapacity((array.size - 1) / 2)
            }
        }
        return result
    }

    protected fun checkCapacity(capacity: Int) {
        if (capacity < MIN_HEAP_CAPACITY) {
            throw IllegalArgumentException("Heap capacity must be >= $MIN_HEAP_CAPACITY")
        }
        if (capacity > MAX_HEAP_CAPACITY) {
            throw IllegalArgumentException("Heap capacity too large")
        }
    }

    protected abstract fun ensureCapacity(capacity: Int)

    protected abstract fun forceFixup(k: Int)

    protected abstract fun fixup(k: Int)

    protected abstract fun fixupWithComparator(k: Int)

    protected abstract fun fixdown(k: Int)

    protected abstract fun fixdownWithComparator(k: Int)

    // handle
    inner class ArrayHandle (override var key: K, override var value: V?) :
        AddressableHeap.Handle<K, V>, Serializable {

        var index: Int = NO_INDEX

        @LogarithmicTime
        override fun decreaseKey(newKey: K) {
            if (index == NO_INDEX) {
                throw IllegalArgumentException("Invalid handle!")
            }

            val c: Int
            if (comparator == null) {
                c = (newKey as Comparable<K>).compareTo(key)
            } else {
                c = comparator!!.compare(newKey, key)
            }
            if (c > 0) {
                throw IllegalArgumentException("Keys can only be decreased!")
            }

            key = newKey
            if (c == 0 || index == 1) {
                return
            }

            if (comparator == null) {
                fixup(index)
            } else {
                fixupWithComparator(index)
            }
        }

        override fun delete() {
            if (index == NO_INDEX) {
                throw IllegalArgumentException("Invalid handle!")
            }

            if (index == 1) {
                deleteMin()
                return
            }

            forceFixup(index)
            deleteMin()
        }

    }

    companion object {
        /**
         * Denotes that a handle is not in the array
         */
        protected val NO_INDEX: Int = -1

        /**
         * The maximum heap capacity.
         */
        protected val MAX_HEAP_CAPACITY: Int = Int.MAX_VALUE - 8 - 1

        /**
         * The minimum heap capacity.
         */
        protected val MIN_HEAP_CAPACITY: Int = 0

        /**
         * Limit for the heap capacity when down-sizing.
         */
        protected val DOWNSIZING_MIN_HEAP_CAPACITY: Int = 16
    }
}
